package Leetcode.动态规划;

//N：多边形边数+1（int[a]范围int[0]~int[a-1]，+1为了方便后面使用N可以直接理解为几条边）
//w[N][N]：记录凸多边形的权值，w[a][b]表示点a和点b之间连线的权值
//s[i][j]表示点i-1到j组成的凸多边形的最优剖分点
//t[i][j] 表示点i-1到j组成的凸多边形的最优三角剖分的解
//https://blog.csdn.net/weixin_42440765/article/details/120766583
public class 凸多边形最优三角剖分 {
    //六边形
    static int N = 7;
    //给定六边形的权值
    static int[][] w = {{0, 2, 2, 3, 1, 4},
                        {2, 0, 1, 5, 2, 3},
                        {2, 1, 0, 2, 1, 4},
                        {3, 5, 2, 0, 6, 2},
                        {1, 2, 1, 6, 0, 1},
                        {4, 3, 4, 2, 1, 0}};

    public static void main(String[] args) {
        MinWeightTriangulation(N, w);
    }

    /**
     * @param N 边长数
     * @param w 各点之间的权值  矩阵
     *          类比矩阵连乘
     */
    public static void MinWeightTriangulation(int N, int[][] w) {
        int[][] s = new int[N][N];//存放最优剖分点k
        int[][] dp = new int[N][N];//存放解
        //初始化
        for (int i = 0; i < N; i++) {
            dp[i][i] = 0;
        }
        //r为间隔边数，先从两条边开始，即三个点组成的凸多边形（三角形）
        for (int r = 2; r < N; r++) {
            //i的范围 (N-1-1)-(i-1)>=r → i<N-r 或 i<=N-r+1，N两次-1分别是：1、初始N为边数加一 2、顶点编号从0开始
            for (int i = 1; i < N - r; i++) {
                int j = i - 1 + r;//j为i加上间隔边数
                dp[i][j] = dp[i][i] + dp[i + 1][j] + Weight(i - 1, i, j);
                s[i][j] = i;//记录k值
                //开始考虑不同的k值
                for (int k = i + 1; k < j; k++) {
                    int min = dp[i][k] + dp[k + 1][j] + Weight(i - 1, k, j);
                    if (min < dp[i][j]) {//有更优解
                        dp[i][j] = min;
                        s[i][j] = k;
                    }
                }
            }
        }
        System.out.println("最优解：" + dp[1][N - 2]);
        Traceback(1, N - 2, s);
    }
    
    static void Traceback(int i, int j, int[][] s) {
        if (i == j) {
            return;
        }
        //子问题的k值
        Traceback(i, s[i][j], s);
        Traceback(s[i][j] + 1, j, s);
        System.out.println("剖分点："+(i - 1) + "  " + j + "  " + s[i][j]);
    }

    public static int Weight(int a, int b, int c) {//求三角形的权值
        return w[a][b] + w[b][c] + w[a][c];
    }
}

